๐Ÿ‘ฉโ€๐Ÿ’ป 15685. ๋“œ๋ž˜๊ณค ์ปค๋ธŒ

@Seongukbaek Posted March 30, 2022 ยท Updated March 30, 2022 ยท 6 min read

๋ฌธ์ œ

๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ธ ๊ฐ€์ง€ ์†์„ฑ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ์ด์ฐจ์› ์ขŒํ‘œ ํ‰๋ฉด ์œ„์—์„œ ์ •์˜๋œ๋‹ค. ์ขŒํ‘œ ํ‰๋ฉด์˜ x์ถ•์€ โ†’ ๋ฐฉํ–ฅ, y์ถ•์€ โ†“ ๋ฐฉํ–ฅ์ด๋‹ค.

  1. ์‹œ์ž‘ ์ 
  2. ์‹œ์ž‘ ๋ฐฉํ–ฅ
  3. ์„ธ๋Œ€

0์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š” ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์€ ๊ธธ์ด๊ฐ€ 1์ธ ์„ ๋ถ„์ด๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ (0, 0)์—์„œ ์‹œ์ž‘ํ•˜๊ณ , ์‹œ์ž‘ ๋ฐฉํ–ฅ์€ ์˜ค๋ฅธ์ชฝ์ธ 0์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์ด๋‹ค.

1์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š” 0์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ๋ ์ ์„ ๊ธฐ์ค€์œผ๋กœ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ 90๋„ ํšŒ์ „์‹œํ‚จ ๋‹ค์Œ 0์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ๋ ์ ์— ๋ถ™์ธ ๊ฒƒ์ด๋‹ค. ๋ ์ ์ด๋ž€ ์‹œ์ž‘ ์ ์—์„œ ์„ ๋ถ„์„ ํƒ€๊ณ  ์ด๋™ํ–ˆ์„ ๋•Œ, ๊ฐ€์žฅ ๋จผ ๊ฑฐ๋ฆฌ์— ์žˆ๋Š” ์ ์„ ์˜๋ฏธํ•œ๋‹ค.

2์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋„ 1์„ธ๋Œ€๋ฅผ ๋งŒ๋“  ๋ฐฉ๋ฒ•์„ ์ด์šฉํ•ด์„œ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. (ํŒŒ๋ž€์ƒ‰ ์„ ๋ถ„์€ ์ƒˆ๋กœ ์ถ”๊ฐ€๋œ ์„ ๋ถ„์„ ๋‚˜ํƒ€๋‚ธ๋‹ค)

3์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋„ 2์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ์ด์šฉํ•ด ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ 3์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์ด๋‹ค.

์ฆ‰, K(K > 1)์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š” K-1์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ๋ ์ ์„ ๊ธฐ์ค€์œผ๋กœ 90๋„ ์‹œ๊ณ„ ๋ฐฉํ–ฅ ํšŒ์ „ ์‹œํ‚จ ๋‹ค์Œ, ๊ทธ๊ฒƒ์„ ๋ ์ ์— ๋ถ™์ธ ๊ฒƒ์ด๋‹ค.

ํฌ๊ธฐ๊ฐ€ 100ร—100์ธ ๊ฒฉ์ž ์œ„์— ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๊ฐ€ N๊ฐœ ์žˆ๋‹ค. ์ด๋•Œ, ํฌ๊ธฐ๊ฐ€ 1ร—1์ธ ์ •์‚ฌ๊ฐํ˜•์˜ ๋„ค ๊ผญ์ง“์ ์ด ๋ชจ๋‘ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ผ๋ถ€์ธ ์ •์‚ฌ๊ฐํ˜•์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๊ฒฉ์ž์˜ ์ขŒํ‘œ๋Š” (x, y)๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, 0 โ‰ค x โ‰ค 100, 0 โ‰ค y โ‰ค 100๋งŒ ์œ ํšจํ•œ ์ขŒํ‘œ์ด๋‹ค.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 20)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ •๋ณด๋Š” ๋„ค ์ •์ˆ˜ x, y, d, g๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. x์™€ y๋Š” ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์‹œ์ž‘ ์ , d๋Š” ์‹œ์ž‘ ๋ฐฉํ–ฅ, g๋Š” ์„ธ๋Œ€์ด๋‹ค. (0 โ‰ค x, y โ‰ค 100, 0 โ‰ค d โ‰ค 3, 0 โ‰ค g โ‰ค 10)
  • ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š” ๊ฒฉ์ž ๋ฐ–์œผ๋กœ ๋ฒ—์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค. ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š” ์„œ๋กœ ๊ฒน์น  ์ˆ˜ ์žˆ๋‹ค.
  • ๋ฐฉํ–ฅ์€ 0, 1, 2, 3 ์ค‘ ํ•˜๋‚˜์ด๊ณ , ๋‹ค์Œ์„ ์˜๋ฏธํ•œ๋‹ค.

    • 0: x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ (โ†’)
    • 1: y์ขŒํ‘œ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ (โ†‘)
    • 2: x์ขŒํ‘œ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ (โ†)
    • 3: y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ (โ†“)

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ํฌ๊ธฐ๊ฐ€ 1ร—1์ธ ์ •์‚ฌ๊ฐํ˜•์˜ ๋„ค ๊ผญ์ง“์ ์ด ๋ชจ๋‘ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ผ๋ถ€์ธ ๊ฒƒ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class DragonMap { int[][] map = new int[101][101]; int[] rangeX = { 1, 0, -1, 0 }; int[] rangeY = { 0, -1, 0, 1 }; ... }
  • ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ๊ทธ๋ฆฌ๊ธฐ ์œ„ํ•œ map ๊ณผ ๋ฐฉํ–ฅ์— ๋”ฐ๋ฅธ ์ด๋™์„ ์œ„ํ•ด ์‚ฌ์šฉํ•˜๋Š” ๋ฒ”์œ„ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค
public void drawDragonCurves(int x, int y, int d, int g) { List<Integer> dirList = new ArrayList<>(); dirList.add(d); for (int i = 0; i < g; i++) { for (int j = dirList.size() - 1; j >= 0; j--) { dirList.add(getCountClockDir(dirList.get(j))); } } map[x][y] = 1; for (Integer dir : dirList) { x += rangeX[dir]; y += rangeY[dir]; map[x][y] = 1; } }
  • ๋ฆฌ์ŠคํŠธ์— ๋ฐฉํ–ฅ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๊ณ , ๋งˆ์ง€๋ง‰์— ์ €์žฅํ•œ ๋ฐฉํ–ฅ ์ •๋ณด๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ๋Œ๋ฆฐ ๋ฐฉํ–ฅ ์ •๋ณด๋ฅผ ์ €์žฅํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; class DragonMap { int[][] map = new int[101][101]; int[] rangeX = { 1, 0, -1, 0 }; int[] rangeY = { 0, -1, 0, 1 }; public void drawDragonCurves(int x, int y, int d, int g) { List<Integer> dirList = new ArrayList<>(); dirList.add(d); for (int i = 0; i < g; i++) { for (int j = dirList.size() - 1; j >= 0; j--) { dirList.add(getCountClockDir(dirList.get(j))); } } map[x][y] = 1; for (Integer dir : dirList) { x += rangeX[dir]; y += rangeY[dir]; map[x][y] = 1; } } public int countSquares() { int counts = 0; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { if (map[i][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) { counts++; } } } return counts; } private int getCountClockDir(int dir) { return (dir + 1) % 4; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); DragonMap dragons = new DragonMap(); for (int i = 0; i < N; i++) { int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); dragons.drawDragonCurves(info[0], info[1], info[2], info[3]); } br.close(); System.out.println(dragons.countSquares()); } }

โœ๏ธ Review

  • ๋งค ์„ธ๋Œ€๋งˆ๋‹ค ๋ฐฉํ–ฅ์ด ๋ฐ”๋€Œ๋Š” ๊ฒƒ์— ๋Œ€ํ•ด, ์ด๋ฅผ ๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ•˜๊ณ  ๊ณ„์† ์—…๋ฐ์ดํŠธํ•ด์ฃผ๋Š” ๋ฐฉ์‹์€ ์ƒ๊ฐํ–ˆ์ง€๋งŒ, ์™œ์ธ์ง€ ๋ฆฌ์ŠคํŠธ๋„ ํ์ฒ˜๋Ÿผ push , pop ์„ ํ•ด์•ผ ํ•˜๋‹ˆ๊นŒ ๋น„ํšจ์œจ์ ์ด์ง€ ์•Š๋‚˜ ... ํ•˜๋Š” ์ƒ๊ฐ์— ์‚ฌ๋กœ์žกํ˜€ ํ˜ผ์ž ๊ฝ‰ ๋ง‰ํ˜€๋ฒ„๋ ธ๋‹ค.
  • ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์€ ๋ญ๊ฐ€ ์žˆ๋‚˜ ์‹ถ์–ด ํ•œ ๋ธ”๋กœ๊ทธ๋ฅผ ๋ดค๋Š”๋ฐ, ์ƒ๊ฐํ•œ ๊ทธ๋Œ€๋กœ๋ฅผ ๊ตฌํ˜„ํ•œ ๊ธ€์„ ๋ฐœ๊ฒฌํ•ด์„œ ๋‚˜์˜ ๋ฌด์ง€ํ•จ์„ ๊นจ๋‹ฌ์•˜๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€